{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"top\"></a><img src=\"images/chisel_1024.png\" alt=\"Chisel logo\" style=\"width:480px;\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Module 4.1: Introduction to FIRRTL\n",
    "\n",
    "**Prev: [Generators: Types](3.6_types.ipynb)**<br>\n",
    "**Next: [FIRRTL AST Traversal](4.2_firrtl_ast_traversal.ipynb)**\n",
    "\n",
    "## Motivation\n",
    "You've learned some Scala and written some Chisel, and for 90% of users, that should be enough to become a Chisel aficionado.\n",
    "\n",
    "However, some use cases are better expressed as a programmatic transformation of a Chisel design, rather than as a generator.\n",
    "\n",
    "For example, suppose we want to count the number of registers in a design. This would be difficult to do as a generator, so instead, we can write a FIRRTL pass to do it for us.\n",
    "\n",
    "## Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "val path = System.getProperty(\"user.dir\") + \"/source/load-ivy.sc\"\n",
    "interp.load.module(ammonite.ops.Path(java.nio.file.FileSystems.getDefault().getPath(path)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import chisel3._\n",
    "import chisel3.util._\n",
    "import chisel3.iotesters.{ChiselFlatSpec, Driver, PeekPokeTester}\n",
    "import firrtl._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is FIRRTL?\n",
    "As you've probably become aware, when you execute a Chisel design, it elaborates (executes the surrounding Scala code) to construct an instance of your generator, with all Scala parameters resolved.\n",
    "\n",
    "Instead of directly emitting Verilog, Chisel emits an intermediate representation called FIRRTL, which represents the elaborated (parameter-resolved) RTL instance. It can be serialized (converted to a String for writing to a file), and this serialized syntax is human readable. Internally, however, it is not represented as a long string. Instead, it is a datastructure organized as a tree of nodes, called an abstract-syntax-tree (AST).\n",
    "\n",
    "Let's take a look! We will take a simple Chisel design, elaborate it, and inspect what FIRRTL it generates!\n",
    "\n",
    "First, we define a Chisel module, which delays its input signal by two cycles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class DelayBy2(width: Int) extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in  = Input(UInt(width.W))\n",
    "    val out = Output(UInt(width.W))\n",
    "  })\n",
    "  val r0 = RegNext(io.in)\n",
    "  val r1 = RegNext(r0)\n",
    "  io.out := r1\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, let's elaborate it, serialize, and print out the FIRRTL it generates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "println(chisel3.Driver.emit(() => new DelayBy2(4)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the serialized FIRRTL looks very similar to what our Chisel design would look like, with all generator parameters resolved."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The FIRRTL AST\n",
    "\n",
    "As mentioned earlier, the FIRRTL representation can be serialized as a String, but internally, it is a datastructure called an AST (abstract syntax tree). This data structure is a tree of nodes, where one node can contain children nodes. There are no cycles in this datastructure.\n",
    "\n",
    "Let's take a look at what the internal datastructure looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "val firrtlSerialization = chisel3.Driver.emit(() => new DelayBy2(4))\n",
    "val firrtlAST = firrtl.Parser.parse(firrtlSerialization.split(\"\\n\").toIterator, Parser.GenInfo(\"file.fir\"))\n",
    "\n",
    "println(firrtlAST)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obviously, the serialization of a datastructure isn't as pretty, but you can see some of the classes and such that internally represent the RTL design. Let's try to pretty that up a bit to make it understandable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "println(stringifyAST(firrtlAST))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the internal datastructure that holds the FIRRTL AST. It is a tree structure whose root node is **Circuit**, which has 3 children: **@[file.fir@2.0]**, **ArrayBuffer**, and **cmd5WrapperHelperDelayBy2**. The following is the definition of `Circuit`'s actual Scala class that was serialized:<a name=\"circuit\"></a><img src=\"images/circuit.png\" alt=\"Circuit case class\" />\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, it has three children nodes: `info: Info`, `Modules: Seq[DefModule]`, and `main: String`. It extends `FirrtlNode`, of which all FIRRTL AST nodes must do. Ignore the `def mapXXXX` functions for now.\n",
    "\n",
    "Many FIRRTL nodes contain an `info: Info` field, which the parser can either insert file information like line number and column number, or insert a `NoInfo` token. In this example, **@[file.fir@2.0]** would refer to the FIRRTL file, line 2, column 0.\n",
    "\n",
    "The following section will outline all of these FIRRTL nodes in detail."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# FIRRTL Node Descriptions\n",
    "\n",
    "This section describes common FirrtlNodes found in [firrtl/src/main/scala/firrtl/ir/IR.scala](https://github.com/ucb-bar/firrtl/blob/master/src/main/scala/firrtl/ir/IR.scala).\n",
    "\n",
    "For more detail on components not mentioned here, please refer to [The FIRRTL Specification](https://github.com/ucb-bar/firrtl/blob/master/spec/spec.pdf).\n",
    "\n",
    "\n",
    "## Circuit\n",
    "Circuit is the root node of any Firrtl datastructure. There is only ever one Circuit, and that Circuit contains a list of module definitions and the name of the top-level module.\n",
    "\n",
    "#### FirrtlNode Declaration\n",
    "```scala \n",
    "Circuit(info: Info, modules: Seq[DefModule], main: String)\n",
    "```\n",
    "\n",
    "#### Concrete Syntax\n",
    "```\n",
    "circuit Adder:\n",
    "  ... //List of modules\n",
    "```\n",
    "#### In-memory Representation\n",
    "```scala\n",
    "Circuit(NoInfo, Seq(...), \"Adder\")\n",
    "```\n",
    "\n",
    "## Module\n",
    "\n",
    "Modules are the unit of modularity within Firrtl and are never directly nested (declaring an instance of a module has its own concrete syntax and AST representation). Each Module has a name, and a list of ports, and a body containing its implementation.\n",
    "\n",
    "#### FirrtlNode declaration\n",
    "```scala\n",
    "Module(info: Info, name: String, ports: Seq[Port], body: Stmt) extends DefModule\n",
    "```\n",
    "\n",
    "#### Concrete Syntax\n",
    "```\n",
    "module Adder:\n",
    "  ... // list of ports\n",
    "  ... // statements\n",
    "```\n",
    "#### In-memory representation\n",
    "```scala\n",
    "Module(NoInfo, \"Adder\", Seq(...), )\n",
    "```\n",
    "\n",
    "## Port\n",
    "A port defines part of a Module's io, and has a name, direction (input or output), and type.\n",
    "\n",
    "#### FirrtlNode Declaration\n",
    "```scala\n",
    "class Port(info: Info, name: String, direction: Direction, tpe: Type)\n",
    "```\n",
    "#### Concrete Syntax\n",
    "```\n",
    "input x: UInt\n",
    "```\n",
    "\n",
    "#### In-memory representation\n",
    "```scala\n",
    "Port(NoInfo, \"x\", INPUT, UIntType(UnknownWidth))\n",
    "```\n",
    "\n",
    "## Statement\n",
    "A statement is used to describe the components within a module and how they interact. Below are some commonly used statements:\n",
    "\n",
    "### Block of Statements\n",
    "A group of statements. Commonly used as the body field in a Module declaration.\n",
    "\n",
    "### Wire Declaration\n",
    "A wire declaration, containing a name and type. It can be both a source (connected *from*) and a sink (connected *to\").\n",
    "#### FirrtlNode declaration\n",
    "```scala\n",
    "DefWire(info: Info, name: String, tpe: Type)\n",
    "```\n",
    "#### Concrete syntax\n",
    "```\n",
    "wire w: UInt\n",
    "```\n",
    "#### In-memory Representation\n",
    "```scala\n",
    "DefWire(NoInfo, \"w\", UIntType(UnknownWidth))\n",
    "```\n",
    "\n",
    "### Register Declaration\n",
    "A register declaration, containing a name, type, clock signal, reset signal, and reset value.\n",
    "#### FirrtlNode declaration\n",
    "```scala\n",
    "DefRegister(info: Info, name: String, tpe: Type, clock: Expression, reset: Expression, init: Expression)\n",
    "```\n",
    "\n",
    "### Connection\n",
    "Represents a directioned connection from a source to a sink. Note that it abides by last-connect-semantics, as described in Chisel.\n",
    "\n",
    "#### FirrtlNode declaration\n",
    "```scala\n",
    "Connect(info: Info, loc: Expression, expr: Expression)\n",
    "```\n",
    "\n",
    "### Other Statements\n",
    "Other statement types like `DefMemory`, `DefNode`, `IsInvalid`, `Conditionally`, and others are omitted here; please refer to [firrtl/src/main/scala/firrtl/ir/IR.scala](https://github.com/freechipsproject/firrtl/blob/master/src/main/scala/firrtl/ir/IR.scala) for more detail.\n",
    "\n",
    "## Expression\n",
    "Expressions represent references to declared components or logical and arithmetic operations. Below are some commonly used expressions:\n",
    "\n",
    "### Reference\n",
    "A reference to a declared component, such as a wire, register, or port. It has a name and type field. Note that it does not contain a pointer to the actual declaration, but instead just contains the name as a String.\n",
    "\n",
    "#### FirrtlNode declaration\n",
    "```scala\n",
    "Reference(name: String, tpe: Type)\n",
    "```\n",
    "\n",
    "### DoPrim\n",
    "An anonymous primitive operation, such as `Add`, `Sub`, or `And`, `Or`, or subword-selection (`Bits`). The type of operation is indicated by the `op: PrimOp` field. Note that the number of required arguments and constants are determined by the `op`.\n",
    "\n",
    "#### FirrtlNode declaration\n",
    "```scala\n",
    "DoPrim(op: PrimOp, args: Seq[Expression], consts: Seq[BigInt], tpe: Type)\n",
    "```\n",
    "\n",
    "### Other Expressions\n",
    "Other expressions including `SubField`, `SubIndex`, `SubAccess`, `Mux`, `ValidIf` etc. are described in more detail in [firrtl/src/main/scala/firrtl/ir/IR.scala](https://github.com/ucb-bar/firrtl/blob/master/src/main/scala/firrtl/ir/IR.scala) and [The FIRRTL Specification](https://github.com/ucb-bar/firrtl/blob/master/spec/spec.pdf).\n",
    "\n",
    "# Back to our example\n",
    "\n",
    "Let's take another look at the FIRRTL AST from our example. Hopefully, the structure of the design makes more sense!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "println(stringifyAST(firrtlAST))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's it for this section! In the next section, we will look at how a FIRRTL transformation walks this AST and modifies it."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala211",
   "nbconvert_exporter": "script",
   "pygments_lexer": "scala",
   "version": "2.11.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
